// https://leetcode-cn.com/problems/minimum-path-sum/
// https://www.bilibili.com/video/BV1pK4y1x7RW?from=search&seid=12038450662839921748
class Solution
{
public:
  int minPathSum(vector<vector<int>> &grid) // grip[i][j]
  {
    if (grid.size() == 0 || grid[0].size() == 0)
      return 0;

    // 传入的二维数组的 长度、宽度
    int rows = grid.size();
    int columns = grid[0].size();

    // 1. dp[i][j] 表示 grid[0][0] 到 grid[i][j] 最小路径和
    auto dp = vector< vector<int> >(rows, vector<int>(columns));

    // 2. 从【左上角】元素开始，所以【最小路径和】就是【他自己】的值
    dp[0][0] = grid[0][0];

    // 3. 确定【第一列】每一个元素的【最小路径和】，只能从【上】往【下】走
    for (int i = 1; i < rows; i++)
    {
      // grid[i][0] 对应的最小路径和 =【前一行】对应的最小路径和 + grid[i][0] 自己的值
      dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    // 4. 确定【第一行】每一个元素的【最小路径和】，只能从【左】往【右】走
    for (int j = 1; j < columns; j++)
    {
      // grid[0][j] 对应的最小路径和 =【前一列】对应的最小路径和 + grid[0][j] 自己的值
      dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    // 5. 最后确定【剩下】所有元素的【最小路径和】
    // - 1) 从【左】到【右】？？？
    // - 2) 从【上】到【下】？？？
    // 取上面两种情况的 最【小】值
    for (int i = 1; i < rows; i++) // 除开 grid[0][…] 第一行
    {
      for (int j = 1; j < columns; j++) // 除开 grid[…][0] 第一列
      {
        // 核心: 控制【最小】路径和
        //
        // grid[i][j] 最小路径和 = 元素自己 + min(自上而下, 自左向右)
        // -------------------
        // 1 2 3
        // 4 5 6
        // 7 8 9
        // -------------------
        //
        // 那么 dp[1][1] = grid[1][1] + min(grid[0][1], grid[1][0])
        dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
      }
    }

    // 6. 返回【最下方】元素对应的【最小路径和】
    return dp[rows - 1][columns - 1];
  }
};